package interview.dp;

import java.util.Scanner;

/**
 * 2022年10月12日-第一题-D路通信 https://blog.codefun2000.com/company/hw/22-10-12/P1216.html
 * 求最长连续公共子串，注意和原力扣的最长公共子串不一样
 */
public class LongestContinuousCommonStr {

    /**
     * 1. 定义dp：dp[i][j]为以s1[i-1]和s2[j-1]结尾的最长连续公共子串长度
     * 2. 状态转移公式：若s1[i-1]==s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1;在这个过程中更新max
     *               若s1[i-1]≠s2[j-1]，则dp[i][j] = 0；
     * 3. 初始化：dp[i][0]=0;dp[0][j]=0;
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        int max = 0;
        for (int i = 1;i <= s1.length();i++) {
            for (int j = 1;j <= s2.length();j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
                else dp[i][j] = 0;
            }
        }
        System.out.println(max);
    }
}
